package kbl.language;

import java.util.Iterator;
import java.util.Map.Entry;
import java.util.TreeMap;
import java.util.TreeSet;

public class DFA implements StrategyNFA2DFA {
	// deterministic finite automaton
	/**
	 * SingletonHolder is loaded on the first execution of
	 * Singleton.getInstance() or the first access to SingletonHolder.INSTANCE,
	 * not before.
	 */
	private DFA() {
	}

	private static class SingletonHolder {
		public static final DFA INSTANCE = new DFA();
	}

	public static DFA getInstance() {
		return SingletonHolder.INSTANCE;
	}

	class NFASet implements Comparable<NFASet> {
		TreeSet<NFAState> NFASet; // need NFAState comparable

		public NFASet(TreeSet<NFAState> nfas) {
			this.NFASet = nfas;
		}

		@Override
		public int compareTo(NFASet o) {
			if (o.NFASet.size() == this.NFASet.size()) {
				Iterator<NFAState> ito = o.NFASet.iterator();
				Iterator<NFAState> ithis = this.NFASet.iterator();
				while (ito.hasNext()) {
					int a = ito.next().getid();
					int b = ithis.next().getid();
					if (a != b) {
						return b - a;
					}
				}
			} else
				return this.NFASet.size() - o.NFASet.size();
			return 0;
		}

		@Override
		public String toString() {
			StringBuffer sb = new StringBuffer();
			for (NFAState s : this.NFASet) {
				sb.append(s.toString() + "|");
			}
			return sb.toString();
		}
	}

	class ReverseDFAMap {
		TreeMap<NFASet, CharacterClass> DFAs = new TreeMap<NFASet, CharacterClass>();

		void addNFAs(NFASet nfas, CharacterClass cc) {
			CharacterClass cc1 = DFAs.get(nfas);
			if (cc1 == null) {
				DFAs.put(nfas, cc);
			} else {
				for (CharRange a : cc.getCharRanges()) {
					cc1.addRange(a);
				}
			}
		}

		void clear() {
			DFAs.clear();
		}

	}

	int DFAcount;
	private DFAState root;
	private ReverseDFAMap optimization = new ReverseDFAMap();
	private CharacterClass ccTobeBrk = new CharacterClass();

	@Override
	public void incDFAcount() {
		this.DFAcount++;
	}

	@Override
	public int getDFAcount() {
		return DFAcount;
	}

	@Override
	public DFAState NFA2DFA(NFAState nfa) {
		TreeSet<NFAState> initialNFAs = new TreeSet<NFAState>();
		buildNFASet(initialNFAs, nfa);
		root = new DFAState(this, initialNFAs);
		buildDFA(root);
		return root;
	}

	@Override
	public boolean match(NFAState nfa, String input) {
		CharRange cr = new CharRange(Character.MIN_VALUE, Character.MIN_VALUE);
		DFAState dfa = NFA2DFA(nfa);
		for (char i : input.toCharArray()) {
			dfa = dfa.match(cr.set(i, i));
			if (dfa == null) {
				return false;
			}
		}
		return dfa.isMatch();
	}

	@Override
	public DFAIterator<testDFAStateWrapper> getIterator() {
		return new DFAWalker(root);
	}

	private void buildDFA(DFAState root) {
		TreeSet<NFAState> list = root.getNFASet();
		if (!root.marked) {
			for (NFAState s : list) {
				if (!s.isMatch()) {
					if (s.getCC() != null) {
						for (CharRange a : s.getCC().getCharRanges()) {
							ccTobeBrk.breakRange(a);
						}
					} else {
						ccTobeBrk.breakRange(new CharRange(s.getChar(), s
								.getChar()));
					}
				}
			}
			// Optimisation
			for (CharRange a : ccTobeBrk.getCharRanges()) {
				CharacterClass DFAcc = new CharacterClass();
				DFAcc.addRange(a);
				optimization.addNFAs(new NFASet(walkNFA(a.low, list)),
						DFAcc);
			}
			for (Entry<NFASet, CharacterClass> entry : optimization.DFAs
					.entrySet()) {
				root.DFAMap.put(entry.getValue(),
						createDFA(entry.getKey().NFASet));
			}
			optimization.clear();
			ccTobeBrk.clear();
			// recursively build
			root.marked = true;
			for (DFAState d : root.DFAMap.values()) {
				buildDFA(d);
			}
		}
	}

	private TreeSet<NFAState> walkNFA(char c, TreeSet<NFAState> list) {
		TreeSet<NFAState> NFAs = new TreeSet<NFAState>();
		for (NFAState s : list) {
			if (s.match(c) && !s.match) {
				buildNFASet(NFAs, s.getOut());
			}
		}
		return NFAs;

	}

	private DFAState createDFA(TreeSet<NFAState> NFAs) {
		DFAState parent, child;
		parent = child = root;
		int i = 0;
		while (child != null) {
			i = compareDFA(child, NFAs);
			if (i < 0) {
				if (child.left == null) {
					parent = child;
				}
				child = child.left;
			} else if (i > 0) {
				if (child.right == null) {
					parent = child;
				}
				child = child.right;
			} else {
				return child;
			}
		}
		DFAState dfa = new DFAState(this, NFAs);
		if (i < 0) {
			parent.left = dfa;
		} else {
			parent.right = dfa;
		}
		return dfa;
	}

	private int compareDFA(DFAState d1, TreeSet<NFAState> d2) {
		int s1 = d1.getNFASet().size();
		int s2 = d2.size();
		if (s1 == s2) {
			Iterator<NFAState> it1 = d1.getNFASet().iterator();
			Iterator<NFAState> it2 = d2.iterator();
			while (it1.hasNext()) {
				int a = it1.next().getid();
				int b = it2.next().getid();
				if (a != b) {
					return b - a;
				}
			}
		} else
			return s1 - s2;
		return 0;
	}

	private void buildNFASet(TreeSet<NFAState> NFAs, NFAState s) {
		if (s.isEpsilon()) {
			buildNFASet(NFAs, s.getOut());
			buildNFASet(NFAs, s.getAltout());
		} else {
			NFAs.add(s);
		}
	}

}
